/**
 * 
 */
package sorting;

import utils.CreateUtils;
import utils.PrintUtils;

/**
 * @author Michael
 *
 */
public class QuickSort {

	
	public static int[] quickSort(int[] arr, int start, int end) {
		if (arr ==  null || arr.length == 0 || start >= end)
			return arr;
		
		int pivot = partition(arr, start, end);
		quickSort(arr, start, pivot-1);
		quickSort(arr, pivot+1, end);
		
		return arr;
	}
	
	public static int partition(int[] arr, int start, int end) {
		assert (arr != null && arr.length > 0 && start < end);
		
		int pivotValue = arr[end];
		int fast = start;
		int slow = start;
		while (fast < end) {
			if (arr[fast] < pivotValue) {
				swap(arr, fast, slow++);
			}
			fast++;
		}
		swap(arr, slow, end);
		
		return slow;
	}
	
	
	public static void swap(int[] arr, int x, int y) {
		if (arr == null || arr.length == 0 || x >= arr.length || y >= arr.length || x == y)
			return;
		int tmp = arr[x];
		arr[x] = arr[y];
		arr[y] = tmp;
	}
	
	
	/**
	 * 
	 */
	public QuickSort() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = CreateUtils.randNonNegIntArray(50, 50);
		PrintUtils.printArray(a);
		PrintUtils.printArray(quickSort(a, 0, a.length - 1));
	}

}
